# 最长重复子数组：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

# 暴力解法会超时
class Solution:
    def findLength(self, nums1: list, nums2: list) -> int:
        """
            暴力解法： 遍历nums1，nums2的所有起始位置，找到他们最长重复子数组
        """
        # 记录最长长度
        ans = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                # 用来记录重复长度
                k = 0
                # 要注意比较时， + k 后的下标不要越界
                while i + k < len(nums1) and j + k < len(nums2) and nums1[i + k] == nums2[j + k]:
                    k += 1
                ans = max(ans, k)                

        return ans

# 动态规划
class Solution:
    def findLength(self, nums1: list, nums2: list) -> int:
        """
            优化暴力解法重复计算当前位置最长重复子数组得问题，使用动态规划
            时间复杂度： O(N×M)。
            空间复杂度： O(N×M)。
        """
        # 记录最长长度
        ans = 0
        m, n = len(nums1), len(nums2)
        # 建立, 因为  根据状态转移方程， dp[i][j] = dp[i+1][j+1]。  当前位置最大重复值是取决于前一个状态的。所以当i,j 大于数组长度，默认为0
        dp = [[0 for i in range(n + 1)] for j in range(m + 1)] 
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                dp[i][j] = dp[i+1][j+1] + 1 if nums1[i] == nums2[j] else 0
                ans = max(ans, dp[i][j])
        
        return ans
'''
    1 2 3
    4 5 6

    dp:
    0 0 0 0
    0 0 0 0
    0 0 0 0
    0 0 0 0
'''

# 滑动窗口
class Solution:
    def findLength(self, nums1: list, nums2: list) -> int:
        """
            优化暴力解法重复计算当前位置最长重复子数组得问题
        """
        # 记录最长长度
        ans = 0
        n, m = len(nums1), len(nums2)

        def find(nums1, nums2, st1, st2):
            """
                该方法的功能是，当两个数组对齐后， 计算重叠部分的，最大重复序列的长度
            """
            k = rst = 0

            while st1 + k < len(nums1) and st2 + k < len(nums2):
                while st1 + k < len(nums1) and st2 + k < len(nums2) and nums1[st1 + k] == nums2[st2 + k]:
                    k += 1
                rst = max(rst, k)

                # 更新。看后续还有没有更长的 重复序列
                st1 = st1 + k + 1
                st2 = st2 + k + 1
                k = 0

                # 优化： 如果后面比较的位数，已经小于当前的 最大重复子串的值了，那就直接退出循环。后面一定小于当前的 rst
                if st1 + k + rst >= len(nums1) or st2 + k + rst >= len(nums2):
                    return rst

            return rst
        
        # 有了上面功能的函数。 我们只需要滑动串口。 依次比较对应的位置即可
        ans = 0
        # 从num1，num2 开头一直滑
        for i in range(len(nums1)):
            ans = max(find(nums1, nums2, i, 0), ans)
            # 优化： 和上面find函数里的一样， 当重叠部分都小于当前的 最长重复子串了，那么肯定可以直接返回，后面不会有更长的了
            if ans > min(len(nums1)-i-1, len(nums2)-1):
                break

        # 从num1，num2 开头 向左滑nums2，滑到 nums2的尾部对着 nums1的头部
        for j in range(len(nums2)):
            ans = max(find(nums1, nums2, 0, j), ans)
            # 优化
            if ans > len(nums2) - j - 1:
                return ans
            
        return ans

nums1 = [1,2,3,2,1, 4, 5]
nums2 = [1,3,3,2,1]
# nums2 = [7,8,9]


